package com.wwz.leetcode;

import org.junit.Test;

public class LeetCode26 {

    public int removeDuplicates(int[] nums) {
        int length = nums.length;
        // 特判
        if (length == 0) {
            return 0;
        }
        if (length == 1) {
            return 1;
        }
        int head = 0;
        int next = head + 1;
        // 剩余量
        int surplus = length - 1;
        int removeCount = 0;
        while (next <= surplus) {
            while (nums[head] == nums[next]) {
                removeCount++;
                if(next == surplus){
                    break;
                }
                // 后面的统一前移
                for (int i = next; i < surplus; i++) {
                    nums[i] = nums[i + 1];
                }
                surplus--;
            }
            head = head + 1;
            next = head + 1;

        }
        return length - removeCount;
    }

    /**
     * 执行用时：0 ms, 在所有Java提交中击败了100.00%的用户
     * 内存消耗：42.9 MB, 在所有Java提交中击败了81.31%的用户
     */
    public int removeDuplicatesLC(int[] nums) {
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            // 右边的指针一直向后移动，左边确定右边不是重复的了在移动到下一位
            // 相当于 i 指针充当了一个标记 就是一会需要换位置的元素位置
            if (nums[i] != nums[j]) {
                nums[i + 1] = nums[j];
                i++;
            }
        }
        // +1 是因为数个数从0开始要补回来
        return i + 1;
    }


    @Test
    public void test() {
        System.out.println(removeDuplicatesLC(new int[]{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}));
//        System.out.println(removeDuplicates(new int[]{1, 1}));
    }
}
